package Top200;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-24 15:23
 */
public class fullJustify68 {
    StringBuffer join(String[] words,int left,int right,String sep){
        StringBuffer sb=new StringBuffer(words[left]);
        for (int i = left+1; i < right; i++) {
            sb.append(sep).append(words[i]);
        }
        return sb;
    }
    String blank(int n){
        String res="";
        for (int i = 0; i < n; i++) {
            res+=" ";
        }
        return res;
    }
    public List<String> fullJustify(String[] words, int maxWidth) {
        LinkedList<String> res=new LinkedList<>();
        int right=0,left=0,n=words.length;
        while (true){
            left=right;
            int sumlen=0;
            //循环确定当前行可以放入的单词数量和范围
            while (right<n&&sumlen+words[right].length()+right-left<=maxWidth){
                sumlen+=words[right++].length();
            }
            //当前行是最后一行,单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right==n){
                StringBuffer sb=join(words,left,n," ");
                sb.append(blank(maxWidth- sb.length()));
                res.add(sb.toString());
                return res;
            }
            int wordNum=right-left;
            int spaceNum=maxWidth-sumlen;

            //当前行只有一个单词
            if (wordNum==1){
                StringBuffer sb=new StringBuffer(words[left]);
                sb.append(blank(maxWidth-sb.length()));
                res.add(sb.toString());
                continue;
            }
            //当前行有多个单词
            int aveSpace=spaceNum/(wordNum-1);
            //空格不能平均分配时，前面的需要多一个空格，多空格的个数
            int extrSpace=spaceNum%(wordNum-1);
            StringBuffer sb=new StringBuffer();
            sb.append(join(words,left,left+extrSpace+1,blank(aveSpace+1)));
            sb.append(blank(aveSpace));
            sb.append(join(words,left+extrSpace+1,right,blank(aveSpace)));
            res.add(sb.toString());
        }
    }
}
